package Stack_Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 王圆豪
 * Date: 2024-10-22
 * Time: 14:04
 */
class Node {
    int data; // 节点数据
    Node next; // 指向下一个节点的指针

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class CircularLinkedQueue {
    private Node head; // 队列的头节点
    private Node tail; // 队列的尾节点
    private int size; // 队列的大小

    public CircularLinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    // 入队
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (size == 0) {
            head = newNode;
            tail = newNode;
            newNode.next = head; // 形成循环
        } else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head; // 形成循环
        }
        size++;
    }

    // 出队
    public int dequeue() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        int data = head.data;
        if (size == 1) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            tail.next = head; // 保持循环
        }
        size--;
        return data;
    }

    // 获取队列的大小
    public int getSize() {
        return size;
    }
}

public class JosephusProblem {
    public static void main(String[] args) {
        int n = 6; // 人数
        int m = 5; // 报数
        solveJosephusProblem(n, m);
    }

    public static void solveJosephusProblem(int n, int m) {
        CircularLinkedQueue queue = new CircularLinkedQueue();

        // 初始化队列
        for (int i = 1; i <= n; i++) {
            queue.enqueue(i);
        }

        System.out.print("出列顺序: ");
        int count = 0; // 计数器

        // 循环出列
        while (queue.getSize() > 0) {
            count = (count + 1) % m; // 计数，m-1后出列
            if (count == 0) {
                System.out.print(queue.dequeue() + " "); // 出列
                count = 0; // 重置计数器
            } else {
                // 将当前元素移到队列尾部
                int person = queue.dequeue();
                queue.enqueue(person);
            }
        }
    }
}